#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>

using namespace std;

// 平方再排序
vector<int> sortedSquares(vector<int>& nums) {
    for (int i = 0, len = nums.size(); i < len; i++) {
        nums[i] *= nums[i];
    }

    sort(nums.begin(), nums.end());

    return nums;
}

// 平方后的结果 两头元素是最大的
// 找到最大的元素一个个填入新数组中即可
vector<int> sortedSquares2(vector<int>& nums) {
    int len = nums.size();
    vector<int> result = vector<int>(len, 0);
    int left = 0, right = len - 1, i = len - 1;
    while (left <= right) {
        if (abs(nums[left]) < abs(nums[right])) {
            result[i--] = nums[right] * nums[right];
            right--;
        } else {
            result[i--] = nums[left] * nums[left];
            left++;
        }
    }

    return result;
}

int main() {
    vector<int> nums = {-1, 0, 3, 5, 9, 12};
    int target = 9;
    vector<int> result = sortedSquares(nums);

    for (int i = 0, len = result.size(); i < len; i++) {
        cout << "nums[" << i << "] = " << result[i] << endl;
    }
}